package cn.zyl.demo.java.sort;

import java.util.Arrays;

/**
 * MergeSort  类说明: 归并排序
 * ---------------------------------------------------------------------------------------------------------
 * <p>归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用</p>
 * <p>为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法</p>
 * <p>--自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）</p>
 * <p>--自下而上的迭代</p>
 * <p>在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：</p>
 * <p>--However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle</p>
 * <p>--然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了</p>
 * <p>不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？</p>
 * <p>和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间</p>
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class MergeSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <p>
     *     算法步骤<br>
     *     1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；<br>
     *     2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；<br>
     *     3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；<br>
     *     4.重复步骤 3 直到某一指针达到序列尾；<br>
     *     5.将另一序列剩下的所有元素直接复制到合并序列尾<br>
     * </p>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        start();
        Integer[] res = merge(sourceArray, order);
        end();
        return res;
    }
    private Integer[] merge(Integer[] sourceArray, Boolean order){
        int len = sourceArray.length;
        Integer[] arr = Arrays.copyOf(sourceArray,len);
        if(len < N_2){return arr;}
        int middle = (int) Math.floor(len/N_2);
        //zuo
        Integer[] left = Arrays.copyOfRange(arr, N_0, middle);
        Integer[] right = Arrays.copyOfRange(arr, middle, len);
        return merge(merge(left, order), merge(right, order), order);
    }
    private Integer[] merge(Integer[] left, Integer[] right, Boolean order) {
        Integer[] res = new Integer[left.length+right.length];
        int i = N_0;
        while (left.length > N_0 && right.length > N_0){
            addOne();
            if(order){
                if(left[N_0] <= right[N_0]){
                    res[i++] = left[N_0];
                    left = Arrays.copyOfRange(left, N_1, left.length);
                }else {
                    res[i++] = right[N_0];
                    right = Arrays.copyOfRange(right, N_1, right.length);
                }
            }else{
                if(left[N_0] <= right[N_0]){
                    res[i++] = right[N_0];
                    right = Arrays.copyOfRange(right, N_1, right.length);
                }else {
                    res[i++] = left[N_0];
                    left = Arrays.copyOfRange(left, N_1, left.length);
                }
            }
        }
        while (left.length > N_0){
            res[i++] = left[N_0];
            left = Arrays.copyOfRange(left, N_1, left.length);
            addOne();
        }
        while (right.length > N_0){
            res[i++] = right[N_0];
            right = Arrays.copyOfRange(right, N_1, right.length);
            addOne();
        }
        return res;
    }
    public static void main(String[] args) {
        int len =15,max=100;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new MergeSort();
        try {
            printArray(arr);
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
